package struct.string;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import java.util.*;

/**
 * @author: kanggw
 * @date: 2022/3/22
 * @DESCRIPTION:
 * 单词拆分
给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

 

示例 1：

输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]
示例 2：

输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
解释: 注意你可以重复使用字典中的单词。
示例 3：

输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
输出:[]

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xa9v8i/

 */
public class WordSplitLevel2 {

    private List<Deque<String>> result = new ArrayList();
    private Deque<String> temp = new LinkedList();

    public List<Deque<String>> wordBreak(String s, List<String> wordDict) {
        if (null == s || s.length() == 0 || null == wordDict || wordDict.size() == 0) {
            return Lists.newArrayList();
        }

        backUp(s,0,wordDict);

        return result;
    }

    public void backUp(String s, int startIndex, List<String> wordDict) {

        if (startIndex >= s.length()) {
            result.add(temp);
            temp = new LinkedList<>();
            return;
        }

        for (int endIndex = startIndex + 1; endIndex <= s.length(); endIndex++) {
            final String substring = s.substring(startIndex, endIndex);
            System.out.println("substring:" + substring);
            if (wordDict.contains(s.substring(startIndex, endIndex))) {
                temp.add(s.substring(startIndex, endIndex));
                backUp(s, endIndex, wordDict);
            }

        }
    }

    public static void main(String[] args) {

        String s = "pineapplepenapple";
        List<String> wordDict = Lists.newArrayList("apple","pen","applepen","pine","pineapple");
        WordSplitLevel2 wordSplitLevel2 = new WordSplitLevel2();
        final List<Deque<String>> deques = wordSplitLevel2.wordBreak(s, wordDict);
        deques.forEach(item ->{
            while (!item.isEmpty()){
                System.out.print(item.pollFirst()+" ");
            }
            System.out.println();
        });
    }


    class Solution {
        public List<String> wordBreak(String s, List<String> wordDict) {
            Map<Integer, List<List<String>>> map = new HashMap<Integer, List<List<String>>>();
            List<List<String>> wordBreaks = backtrack(s, s.length(), new HashSet<String>(wordDict), 0, map);
            List<String> breakList = new LinkedList<String>();
            for (List<String> wordBreak : wordBreaks) {
                breakList.add(String.join(" ", wordBreak));
            }
            return breakList;
        }

        public List<List<String>> backtrack(String s, int length, Set<String> wordSet, int index, Map<Integer, List<List<String>>> map) {
            if (!map.containsKey(index)) {
                List<List<String>> wordBreaks = new LinkedList<List<String>>();
                if (index == length) {
                    wordBreaks.add(new LinkedList<String>());
                }
                for (int i = index + 1; i <= length; i++) {
                    String word = s.substring(index, i);
                    if (wordSet.contains(word)) {
                        List<List<String>> nextWordBreaks = backtrack(s, length, wordSet, i, map);
                        for (List<String> nextWordBreak : nextWordBreaks) {
                            LinkedList<String> wordBreak = new LinkedList<String>(nextWordBreak);
                            wordBreak.offerFirst(word);
                            wordBreaks.add(wordBreak);
                        }
                    }
                }
                map.put(index, wordBreaks);
            }
            return map.get(index);
        }
    }

}

